import java.util.Scanner;

/**
 * Author: 王俊超
 * Time: 2016-05-07 12:14
 * CSDN: http://blog.csdn.net/derrantcm
 * Github: https://github.com/Wang-Jun-Chao
 * Declaration: All Rights Reserved !!!
 */
public class Main {
    public static void main(String[] args) {
        int[] preOrder={1,2,4,7,3,5,6,8};
        int[] inOrder={4,7,2,1,5,3,8,6};
        BinaryTreeNode node = reConstructBinaryTree(preOrder, inOrder);
        System.out.println("=========后序遍历的输出结果=========");
        printBinaryTreeByLast(node);

        System.out.println();
        System.out.println("=========先序遍历的输出结果=========");
        printBinaryTreeByPre(node);
    }

    public static BinaryTreeNode reConstructBinaryTree(int[] preOrder,int[] inOrder){
        if(preOrder==null || inOrder == null || preOrder.length!=inOrder.length || preOrder.length<1){
            return null;
        }
        return reBuild(preOrder,0,preOrder.length-1,inOrder,0,inOrder.length-1);
    }

    /**
     * 重新构建二叉树
     * @param preOrder 先序遍历的二叉树数据
     * @param ps 先序遍历的起点
     * @param pe 先序遍历的终点
     * @param inOrder 中序遍历的二叉树数据
     * @param is 中序遍历起点
     * @param ie 中序遍历终点
     */
    public static BinaryTreeNode reBuild(int[] preOrder,int ps,int pe,int[] inOrder,int is,int ie){
        //开始节点大于结束节点，说明已经结束了
        if(ps>pe)
            return null;
        //先序遍历的起始位置是根节点
        int rootValue = preOrder[ps];
        //用于记录根节点在中序遍历时的位置,初始设为is
        int index = is;
        while(index<ie && inOrder[index] != rootValue){
            index++;
        }
        //如果中序遍历完还没找到根节点，说明二叉树初始化数据错误
        if(index>ie){
            throw new RuntimeException("中序遍历初始化存在错误");
        }

        //递归调用构建二叉树
        BinaryTreeNode node = new BinaryTreeNode();
        node.value = rootValue;

        //当前节点左子树的个数【index-is】
        //当前节点在先序遍历的起始位置【preOrder,ps+1,ps+index-is】
        //当前节点在中序遍历的起始位置【inOrder,is,index-1】
        int num = index - is;
        node.leftNode = reBuild(preOrder,ps+1,ps+index-is,inOrder,is,index-1);

        //当前节点右子树的个数【ie-index】
        //当前节点在先序遍历的起始位置【preOrder,ps+index-is+1,pe】
        //当前节点在后序遍历的起始位置【inOrder,index+1,ie】
        node.rightNode = reBuild(preOrder,ps+index-is+1,pe,inOrder,index+1,ie);
        return node;
    }



    /**
     * 后序输出
     * @param node
     */
    public static  void printBinaryTreeByLast(BinaryTreeNode node){
        if(node!=null){
            printBinaryTreeByLast(node.leftNode);
            printBinaryTreeByLast(node.rightNode);
            System.out.print(node.value+" ");
        }
    }

    /**
     * 先序输出
     * @param node
     */
    public static  void printBinaryTreeByPre(BinaryTreeNode node){
        if(node!=null){
            System.out.print(node.value+" ");
            printBinaryTreeByPre(node.leftNode);
            printBinaryTreeByPre(node.rightNode);
        }
    }
    /**
     * 二叉树节点
     */
    static class BinaryTreeNode{
        int value;
        BinaryTreeNode leftNode;
        BinaryTreeNode rightNode;
    }

}
